package com.zang.backtrack;

import io.github.vampireachao.stream.core.lambda.function.SerPred;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 组合总和
 * @author ZVerify
 * @since 2022/11/13 09:37
 * @see <a href="https://leetcode.cn/problems/combination-sum/">...</a>
 **/
public class 组合总和 {

    // 返回值
    List<List<Integer>> result = new ArrayList<>();
    // 结果集
    List<Integer> list = new ArrayList<>();
    int sum = 0;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {


        backTracking(candidates,target,0);
        Arrays.sort(candidates);
        return result;
    }

    private void backTracking(int[] candidates, int target, int startIndex) {

        if (sum == target) {
            // 相等的时候添加
            result.add(new ArrayList<>(list));
            return;
        }

        for (int j = startIndex; j < candidates.length; j++) {

            // 如果大于的话直接退出此层，因为已经排好序了，后边肯定都会大的
            if (sum+candidates[j]>target) break;
            sum+=candidates[j];
            list.add(candidates[j]);
            backTracking(candidates,target,j);
            // 回溯
            sum-=candidates[j];
            list.remove(list.size()-1);
        }
    }

}
